"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, next, random):
        self.val = val
        self.next = next
        self.random = random
"""


class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if not head:
            return None
        new_head = Node(head.val, None, None)

        new_head_copy = new_head
        stack = []
        stack.append(head)
        stack.append(new_head)
        nodes = head.next
        while nodes:
            cur_node = Node(nodes.val, None, None)
            stack.append(nodes)
            stack.append(cur_node)
            new_head_copy.next = cur_node
            new_head_copy = cur_node
            nodes = nodes.next
        for i in range(len(stack)):
            if i % 2:
                continue
            else:
                if stack[i].random:
                    stack[i+1].random = stack[stack.index(stack[i].random) + 1]
                else:
                    stack[i+1].random = None
        return new_head

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, next, random):
        self.val = val
        self.next = next
        self.random = random
"""


class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if not head:
            return head
        head_copy = head

        while head_copy:
            next_node = head_copy.next
            cur_node = Node(head_copy.val, next_node, None)
            head_copy.next = cur_node
            head_copy = next_node
   
       
        head_copy = head
        while head_copy:
            cur_node = head_copy.next
            if head_copy.random:
                cur_node.random = head_copy.random.next
            head_copy = head_copy.next.next
        head_copy_ini  = head
        head_copy_new = head.next
        res_head = head.next

        while head_copy_new :

            head_copy_ini.next = head_copy_ini.next.next
            if head_copy_new.next:
                head_copy_new.next = head_copy_new.next.next
            
            head_copy_ini = head_copy_ini.next
            head_copy_new = head_copy_new.next
        return res_head
